package com.cn.codebrush.leetcode.editor.cn;
// 2022-11-10 10:56:58
// 22  括号生成
//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 字符串 动态规划 回溯 
// 👍 2947 👎 0


import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

public class GenerateParentheses{

public static void main(String[] args) {

Solution solution = new GenerateParentheses().new Solution();
    System.out.println(solution.generateParenthesis(3));

}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 可以使用回溯的方法来实现这个题目，先回溯左边的括号，返回标志是 n=0,同样右边也是，
    // l == 0 && r == 0 时 加入 list
    // l > r 时返回,因为右边括号不能比左边多
    // 最终输出list
    List<String> resList = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        generateParenthesisHelper(n,n,"");
        return resList;
    }
    public void generateParenthesisHelper(int l,int r,String str) {
        if(l == 0 && r == 0){
            resList.add(str);
            return;
        }
        if(l < 0){
            return;
        }
        if(r < 0){
            return;
        }
        if(l > r){
            return;
        }

        generateParenthesisHelper(l-1,r,str+"(");
        generateParenthesisHelper(l,r-1,str+")");
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}